/**
 * 剑指 Offer 63. 股票的最大利润
 * https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/
 */

/**
 * @param {number[]} prices
 * @return {number}
 */
function maxProfit(prices) {
  const stack = new Array(prices.length);
  let top = -1;
  let max = 0;
  for (let i = 0; i < prices.length; i += 1) {
    while (top >= 0 && prices[i] < stack[top]) {
      top -= 1;
    }
    top += 1;
    stack[top] = prices[i];
    max = Math.max(max, stack[top] - stack[0]);
  }
  return max;
}

console.log(maxProfit([7, 1, 5, 3, 6, 4]) === 5);
console.log(maxProfit([7, 6, 4, 3, 1]) === 0);
